package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

/**
 * @author feizns
 * @since 2020/3/13
 */
public class SubtreeWithAllDeepest {

    public static void main(String[] args) {
    }

    static Map<TreeNode, TreeNode> parents = new HashMap<>();
    static TreeMap<Integer, Set<TreeNode>> death = new TreeMap<>();
    public static TreeNode subtreeWithAllDeepest(TreeNode root) {
        dfs(root, null, 0);
        Set<TreeNode> value = death.lastEntry().getValue();
        while ( value.size() > 1 ) {
            TreeNode[] nodes = value.toArray(new TreeNode[]{});
            for (int i = 0; i < nodes.length; i++) {
                TreeNode parent = parents.get(nodes[i]);
                value.add(parent);
                value.remove(nodes[i]);
            }
        }
        return (TreeNode) value.toArray()[0];
    }

    private static void dfs(TreeNode node, TreeNode parent, int d) {
        if ( node != null ) {
            parents.put(node, parent);
            Set<TreeNode> nodes = death.get(d);
            if ( nodes == null )
                nodes = new HashSet<>();
            nodes.add(node);
            death.put(d, nodes);

            dfs(node.left, node, d + 1);
            dfs(node.right, node, d + 1);
        }
    }

}
